package com.whiteseason.sortdemo;

import sun.plugin2.message.PrintAppletMessage;

import java.util.LinkedList;

/**
 * 归并排序
 */
public class MergeSort {
    public LinkedList<Integer> merge(LinkedList<Integer> left,LinkedList<Integer> right){
        System.out.println("left:"+left.size()+"\tright:"+right.size());
        LinkedList<Integer> result = new LinkedList<>();
        while (left.size() > 0 && right.size() > 0){
            if(left.peekLast() <= right.peekLast()){
                result.push(left.pollLast());
            }else {
                result.push(right.pollLast());
            }
        }

        while(left.size() != 0)
            result.push(left.pollLast());
        while(right.size() != 0)
            result.push(right.pollLast());

        return result;
    }
    public LinkedList<Integer> count(LinkedList<Integer> arr){
        LinkedList<Integer> result = new LinkedList<>();
        int len = arr.size();
        if (arr.size() < 2){
            result.push(arr.pop());
            return result;
        }else {
            LinkedList<Integer> left = new LinkedList<>();
            LinkedList<Integer> right = new LinkedList<>();
            int middle = Math.floorDiv(arr.size(), 2);
            for (int i = 0; i < middle; i++) {
                left.push(arr.pop());
            }
            for (int i = middle; i < len; i++) {
                right.push(arr.pop());
            }
            return merge(count(left),count(right));
        }
    }

    public static void main(String[] args) {

        LinkedList<Integer> arr = new LinkedList<Integer>(){
            {
                add(1);
                add(9);
                add(7);
                add(4);
                add(2);
                add(5);
                add(10);
                add(8);
                add(11);
                add(2);
                add(45);
                add(21);
            }
        };
        LinkedList<Integer> count = new MergeSort().count(arr);
        while(count.size() != 0){
            System.out.println(count.pollLast());
        }
    }
}
